package com.gozap.tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * 树的搜索算法
 * 
 * @author yaoming
 * @date 2013-1-21 下午05:02:26
 * @since JDK1.6
 * @version 2.0.0
 */
public class TreeSearch {

	/**
	 * 创建树
	 * 
	 * @return
	 */
	public Tree buildTree() {
		int len = arr.length;
		Map<Integer, Tree> map = new HashMap<Integer, Tree>();

		for (int i = 0; i < len; i++) {
			Tree tree = map.get(i);
			if (tree == null) {
				tree = new Tree();
				tree.setKey(arr[i]);
				map.put(i, tree);
			}

			int leftIndex = (i + 1) * 2 - 1;
			int rightIndex = (i + 1) * 2;

			if (leftIndex < len) {
				Tree leftTree = new Tree();
				leftTree.setKey(arr[leftIndex]);
				tree.setLeftTree(leftTree);
				map.put(leftIndex, leftTree);
			}

			if (rightIndex < len) {
				Tree rightTree = new Tree();
				rightTree.setKey(arr[rightIndex]);
				tree.setRightTree(rightTree);
				map.put(rightIndex, rightTree);
			}

		}

		return map.get(0);
	}

	int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };

	/** 打印数组 */
	private void printList(List<Tree> list) {
		for (Tree data : list) {
			System.out.print(data.getKey() + " ");
		}
	}

	/**
	 * 树的广度优先搜索算法，白色代表未搜索的；灰色代表也就搜索，但是未全部搜索的；黑色代表全部搜索的 使用t代表灰色的当前index
	 */
	public void brenchSearchTree(Tree tree) {
		// 创建空的栈
		List<Tree> stack = new ArrayList<Tree>();
		stack.add(tree);

		// 标识当前该处理下标
		int i = 0;

		boolean flag = true;
		// 临时存值
		Tree t;
		while (flag) {
			t = stack.get(i);

			Tree leftTree = t.getLeftTree();
			if (leftTree != null) {
				stack.add(leftTree);
			}
			Tree rightTree = t.getRightTree();
			if (rightTree != null) {
				stack.add(rightTree);
			}

			i++;
			if (i >= stack.size()) {
				flag = false;
			}
		}
		printList(stack);
	}

	/**
	 * 深度优先遍历，循环遍历方式,此方式为后序遍历
	 */
	public void deepSearchTreeLoop(Tree tree) {
		// 存储数据
		// List<Tree> list = new ArrayList<Tree>();

		// 临时存储
		LinkedList<Tree> stack = new LinkedList<Tree>();
		stack.push(tree);

		Tree t;
		while (!stack.isEmpty()) {
			t = stack.pop();
			Tree leftTree = t.getLeftTree();
			if (leftTree != null) {
				t.setLeftTree(null);
				stack.push(t);
				stack.push(leftTree);
			} else {
				Tree right = t.getRightTree();
				if (right == null) {
					System.out.print(t.getKey() + " ");
				} else {
					t.setRightTree(null);
					stack.push(t);
					stack.push(right);
				}
			}
		}
	}

	/**
	 * 深度优先遍历，递归方式遍历，此方式为中序遍历
	 */
	public void deepSearchTreeRecur(Tree tree) {
		if (tree != null) {
			Tree leftTree = tree.getLeftTree();

			deepSearchTreeRecur(leftTree);

			System.out.print(tree.getKey() + " ");

			Tree rightTree = tree.getRightTree();

			deepSearchTreeRecur(rightTree);
		}

	}

	public static void main(String[] args) {
		TreeSearch brench = new TreeSearch();
		Tree tree = brench.buildTree();
		// brench.deepSearchTreeRecur(tree);
		// brench.deepSearchTreeLoop(tree);
		brench.brenchSearchTree(tree);
	}
}
